L2-007 家庭房产
题目 L2-007 家庭房产
思路分析
并查集
代码实现
#include<bits/stdc++.h>
using namespace std;
// 宏定义及别名简化代码
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
// 定义四个方向（上下左右），可用于图遍历（虽然这里没用到）
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
// 预留但当前未用的数据结构
priority_queue<int> pq;
multimap<int,int> mp;
const int MAXN=10010; // 最大编号范围
// 并查集结构体
struct DSU{
vector<int> parent;
// 初始化，每个编号自成一个集合
DSU(int n){
parent.resize(n+1);
for(int i=0;i<=n;i++){
parent[i]=i;
}
}
// 查找根节点 + 路径压缩
int find(int x){
if(parent[x]!=x) parent[x]=find(parent[x]);
return parent[x];
}
// 合并两个集合
void unite(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
parent[fx]=fy;
}
}
// 判断两个节点是否属于同一集合
bool connected(int x,int y){
return find(x)==find(y);
}
};
// 家庭结构体，用于储存每个家庭的信息
struct Family{
int id; // 家庭成员中最小编号
int count; // 家庭人口数
double totalEstate; // 房产总数
double totalArea; // 总面积
Family(int id = 0, int c = 0, double te = 0, double ta = 0)
: id(id), count(c), totalEstate(te), totalArea(ta) {}
// 排序方式：人均面积降序，若相同则编号升序
bool operator<(const Family& other) const{
if(fabs(totalArea/count - other.totalArea/other.count)>1e-6)
return totalArea/count > other.totalArea/other.count;
return id<other.id;
}
};
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
DSU dsu(MAXN); // 初始化并查集
// 存储每个编号是否存在
vector<int> exist(MAXN,0);
// 储存每个编号的房产套数和面积
vector<double> estate(MAXN,0),area(MAXN,0);
vector<int> people; // 所有涉及过的人
// 读入每组数据，建立家庭成员之间的联系
for(int i=0;i<n;i++){
int id,fa,mo,k;
cin>>id>>fa>>mo>>k;
exist[id]=1;
people.push_back(id);
// 父亲并入集合
if(fa!=-1){
dsu.unite(id,fa);
exist[fa]=1;
people.push_back(fa);
}
// 母亲并入集合
if(mo!=-1){
dsu.unite(id,mo);
exist[mo]=1;
people.push_back(mo);
}
// 子女并入集合
for(int j=0;j<k;j++){
int child;cin>>child;
dsu.unite(id,child);
exist[child]=1;
people.push_back(child);
}
// 输入该人拥有的房产信息
int sets; double ar;
cin>>sets>>ar;
estate[id]+=sets;
area[id]+=ar;
}
map<int,Family> families; // 用于按家庭根节点记录汇总信息
map<int,int> min_id; // 每个集合中最小编号的成员
// 遍历所有出现过的编号，统计每个家庭的信息
for(int i=0;i<MAXN;i++){
if(!exist[i]) continue;
int root = dsu.find(i); // 找出集合代表
// 若首次遇到该集合
if(families.find(root)==families.end()){
families[root]=Family(i,1,estate[i],area[i]);
min_id[root]=i;
}else{
// 累加集合中的其他成员信息
families[root].count++;
families[root].totalEstate+=estate[i];
families[root].totalArea += area[i];
min_id[root] = min(min_id[root], i); // 保证最小编号正确
}
}
// 把map结构转换为vector并排序，方便输出
vector<Family> res;
for (auto &it : families) {
int id = min_id[it.first];
auto fam = it.second;
fam.id = id;
res.push_back(fam);
}
sort(res.begin(), res.end()); // 按人均面积排序
// 输出家庭数量
printf("%d\n",res.size());
// 输出每个家庭的信息
for (auto &f : res) {
// 编号补零至4位，保留三位小数
printf("%04d %d %.3lf %.3lf\n", f.id, f.count,
f.totalEstate / f.count, f.totalArea / f.count);
}
return 0;
}
同类题型
视频讲解
⬅️ 性质 🏠 00-天梯赛 ➡️ L2-008 最长对称子串
💬 评论